#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <queue>
#include <set>
using namespace std;
int dist(pair<int, int> &p1, pair<int, int> &p2)
{
    return abs(p1.first - p2.first) + abs(p2.second - p1.second);
}
class Solution
{
public:
    int cutOffTree(vector<vector<int>> &forest)
    {
        vector<pair<int, pair<int, int>>> tree;
        for (int m = 0; m < forest.size(); m++)
        {
            for (int n = 0; n < forest[0].size(); n++)
            {
                if (forest[m][n] > 1)
                    tree.push_back(pair<int, pair<int, int>>(forest[m][n], pair<int, int>(m, n)));
            }
        }
        sort(tree.begin(), tree.end(), [](pair<int, pair<int, int>> &p1, pair<int, pair<int, int>> &p2) -> bool {
            return p1.first < p2.first;
        });
        int res = 0;
        pair<int, int> start = {0, 0};
        for (auto t : tree)
        {
            auto tmp = findpath(forest, start, t.second);
            //forest[t.second.first][t.second.second]=1;
            if (tmp == -1)
                return -1;
            cout << tmp << endl;
            res += tmp;
            start = t.second;
        }
        return res;
    }

private:
    int findpath(vector<vector<int>> &forest, pair<int, int> &p1, pair<int, int> &p2)
    {
        class pos
        {
        public:
            pair<int, int> p;

            int g, h;
            pos(pair<int, int> &p1, int p3, int p4) : p(p1), g(p3), h(p4)
            {
            }
            /* data */
        };
        class cmp //重写仿函数
        {

        public:
            bool operator()(pos &a, pos &b)
            {
                return (a.g + a.h) >
                       (b.g + b.h);
            }
        };

        // cout << p1.first << " " << p1.second << " to:" << p2.first << "  " << p2.second << endl;
        priority_queue<pos, vector<pos>, cmp> path; //小顶堆

        //queue<pair<int, int>> path, oldpath;
        //oldpath.push(p1);

        path.push(pos(p1, 0, dist(p1, p2)));

        int m = forest.size(), n = forest[0].size();
        set<int> visited;

        while (!path.empty())
        {
            auto p = path.top();
            path.pop();

            int x = p.p.first, y = p.p.second;

            visited.insert(x * n + y);
            if (p.p == p2)
                return p.g;

            if ((x + 1 < m) && forest[x + 1][y] && visited.count((x + 1) * n + y) == 0)
            {
                pair<int, int> _pair(x + 1, y);
                pos tmp(_pair, p.g + 1, dist(_pair, p2));
                path.push(tmp);
            }
            if ((x - 1 >= 0) && forest[x - 1][y] && visited.count((x - 1) * n + y) == 0)
            {
                pair<int, int> _pair(x - 1, y);
                pos tmp(_pair, p.g + 1, dist(_pair, p2));
                path.push(tmp);
            }
            if ((y + 1 < n) && forest[x][y + 1] && visited.count(x * n + y + 1) == 0)
            {
                pair<int, int> _pair(x, y + 1);
                pos tmp(_pair, p.g + 1, dist(_pair, p2));
                path.push(tmp);
            }
            if ((y - 1 >= 0) && forest[x][y - 1] && visited.count(x * n + y - 1) == 0)
            {
                pair<int, int> _pair(x, y - 1);
                pos tmp(_pair, p.g + 1, dist(_pair, p2));
                path.push(tmp);
            }
        }

        return -1;
    }
};

int main()
{
    Solution a;
    vector<vector<int>> forest =
       {{73177,25859,48546,44398,0,43258,97122,89958,10015,20898,64820,87293,17249,6391,49705,11017,90979,60952,8595,52499,55821,0},
{1089,45310,0,25522,11362,0,65997,2259,67315,39806,51888,36703,27524,26991,48196,66467,7405,21721,48936,84886,72918,47577},
{0,64500,15336,97058,23764,68718,65840,87223,17156,81947,33149,90151,88424,75471,0,33091,93209,45367,69697,14349,0,14183},
{42066,55061,81003,32157,81449,21170,43986,80127,85423,97425,89192,78673,85575,27963,53526,0,0,55424,36521,74924,44238,92119},
{59096,54148,74036,0,69665,11295,0,0,0,61910,26992,24048,41928,86682,37876,48250,39531,21413,64976,62424,0,48233},
{85689,0,49754,9076,21228,51224,84205,96275,0,35346,48224,87861,62431,4241,57760,98843,28525,49052,77358,70132,66935,82242},
{11466,80934,74310,84677,61877,75129,65359,93775,12865,63290,37990,0,12680,50002,0,43456,14309,34683,24132,0,82289,89891},
{3622,56408,80057,0,82350,20560,37854,30255,0,0,97761,56309,66542,6816,38137,64751,35866,67678,23595,50354,76851,11372},
{69273,69541,1786,26045,62434,78292,63356,0,22502,0,20024,0,0,49706,48473,81579,16205,99010,7767,0,19278,0},
{52900,51393,20569,56701,86617,3328,21958,35541,9408,96586,71442,77991,30367,79828,32677,77520,8939,44163,65353,70856,37160,0},
{15007,0,99863,60594,67689,64017,37552,52164,36250,98960,9336,5598,70343,38631,14176,32508,43555,49304,60871,7533,0,93428},
{96502,48246,55050,59744,0,73851,6279,47426,89297,44825,24244,72587,13488,5154,78536,82475,0,93981,33281,23148,77915,95680},
{29864,51020,26461,55532,37299,98091,73886,39527,0,86518,6109,36579,28160,70750,95066,50091,65634,17634,93435,18644,10760,79992},
{75144,58388,64104,0,87761,12221,55196,91078,9155,78451,94603,10051,0,81834,27440,21653,62758,76840,0,98554,69032,6489},
{0,88892,70574,80001,57077,96853,87328,27539,0,11704,85746,26518,64145,80665,16052,97702,45398,63375,33982,8780,0,68822},
{30196,77703,43120,91231,0,13660,82584,44346,21788,12088,0,26750,63121,57558,5914,31588,3498,42563,99084,54839,50100,12128},
{4329,88151,85682,0,75773,95757,93633,31907,59859,18613,43573,32295,77211,44242,83589,34188,43195,91278,81236,99859,92152,34070},
{59625,42542,0,46476,13869,54908,29072,49263,8703,52975,76361,46492,36829,4422,64716,96649,13347,37814,31734,0,6543,87910},
{37053,79135,25864,0,83730,48273,55144,77519,7269,91110,54231,51276,6393,30413,46758,12522,31116,0,77695,56285,10640,50523},
{37914,38217,36930,89296,7619,0,17711,1391,84998,41261,61701,32114,35860,50653,0,35210,68413,0,39630,21319,0,5258},
{67541,65729,52262,96930,97492,59066,92849,73283,24681,75630,19646,67840,93151,54500,0,0,30730,2401,0,30809,0,3977},
{1835,62855,84036,0,13505,0,45413,87903,5304,0,11940,85116,82471,0,38332,73992,64721,89529,93285,75514,19384,42518},
{59941,25963,8179,96199,0,0,1986,78866,71483,9233,895,28507,62989,12310,21246,26078,33087,43584,91071,22460,72069,85637},
{82083,489,24595,15533,46827,87481,26203,97132,48579,15708,4413,98737,0,26482,69928,53828,23619,27525,54343,70491,39804,0}};

    auto c = a.cutOffTree(forest);
    cout << c;
    return 0;
}